587C - Duff in the Army - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define P(x) push_back(x)
#define V vector<int>
int n,m,q;
V v[100050],a[100050],ans,r[100050][20];
int d[100050],f[100050][20];
void dfs(int x,int p)
{
	d[x]=d[p]+1;f[x][0]=p;r[x][0]=a[p];
	for(int i=0;i<v[x].size();i++)
		if(v[x][i]!=p)dfs(v[x][i],x);
}
void M(V a,V b,V &c)
{
	int la=a.size(),lb=b.size(),i=0,j=0;
	while(i+j<10&&i+j<la+lb)
	{
		if(i==la)c.P(b[j++]);
		else if(j==lb)c.P(a[i++]);
		else if(a[i]<=b[j])c.P(a[i++]);
		else c.P(b[j++]);
	}
}
void M(V b)
{
	for(int i=0,l=b.size();i<l;i++)ans.P(b[i]);
}
void Init()
{
	for(int i=1;i<=16;i++)
		for(int j=1;j<=n;j++)
		{
			M(r[j][i-1],r[f[j][i-1]][i-1],r[j][i]);
			f[j][i]=f[f[j][i-1]][i-1];
		}
}
void Sol()
{
	int x,y,k;
	scanf("%d%d%d",&x,&y,&k);
	ans.clear();
	if(d[x]<d[y])swap(x,y);
	int rx=x,ry=y;
	for(int i=16,dis=d[x]-d[y];i>=0;i--)
		if((1<<i)&dis)
		{
			M(r[x][i]);
			x=f[x][i];
		}
	if(x!=y)
	{
		for(int i=16;i>=0;i--)if(f[x][i]!=f[y][i])
		{
			M(r[x][i]);x=f[x][i];
			M(r[y][i]);y=f[y][i];
		}
		M(a[rx]);M(a[ry]);
		M(a[f[x][0]]);
	}
	else M(a[rx]);
	k=min((int)ans.size(),k);
	sort(ans.begin(),ans.end());
	printf("%d",k);
	for(int i=0;i<k;i++)printf(" %d",ans[i]);
	puts("");
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		v[x].P(y);
		v[y].P(x);
	}
	for(int i=1,x;i<=m;i++)
	{
		scanf("%d",&x);
		if(a[x].size()<10)a[x].P(i);
	}
	dfs(1,0);
	Init();
	while(q--)Sol();
}